# 定义C3线性化算法函数，计算类的MRO
def c3_mro_algorithm(cls, debug=False):
    # 文档字符串，说明函数用途和参数
    """
    C3线性化算法实现

    参数:
        cls: 要计算MRO的类
        debug: 是否显示调试信息

    返回:
        该类的MRO列表
    """
    # 如果当前类是object，直接返回[object]
    if cls is object:
        return [object]

    # 如果开启调试，打印当前正在计算的类名
    if debug:
        print(f"\n计算 {cls.__name__} 的MRO:")

    # 创建一个空列表，用于存储所有父类的MRO
    bases_mros = []
    # 遍历当前类的所有直接父类
    for base in cls.__bases__:
        # 递归计算父类的MRO
        base_mro = c3_mro_algorithm(base, debug)
        # 添加该父类的MRO到列表
        bases_mros.append(base_mro)
        # 如果开启调试，打印父类的MRO序列
        if debug:
            print(
                f"  {cls.__name__} 的父类 {base.__name__} 的MRO: {[c.__name__ for c in base_mro]}"
            )

    # 将当前类自身作为第一个MRO列表插入
    bases_mros.insert(0, [cls])

    # 如果开启调试，打印所有合成的MRO列表
    if debug:
        print(f"  所有MRO列表: {[[c.__name__ for c in mro] for mro in bases_mros]}")

    # 调用merge_mro_lists将所有父类MRO和本类合并
    result = merge_mro_lists(bases_mros, debug)

    # 如果开启调试，打印最终MRO
    if debug:
        print(f"  {cls.__name__} 的最终MRO: {[c.__name__ for c in result]}")

    # 返回最终合成的MRO
    return result


# 合并多个MRO列表，按照C3算法规则
def merge_mro_lists(mro_lists, debug=False):
    # 文档字符串，说明函数用途及算法规则
    """
    合并多个MRO列表

    算法规则：
    1. 从第一个列表的第一个元素开始检查
    2. 如果某个类在所有列表中都出现在第一个位置（或者不在某些列表的头部但符合条件）
    3. 将该类添加到结果中，并从所有列表中移除
    4. 重复直到所有列表为空
    """
    # 初始化结果列表
    result = []

    # 循环直到所有MRO列表被处理完
    while any(mro_lists):
        # 如果开启调试，打印当前所有MRO列表
        if debug:
            print(
                f"    当前MRO列表: {[[c.__name__ for c in lst] for lst in mro_lists if lst]}"
            )

        # 查找下一个满足C3规则的候选类
        candidate = find_candidate(mro_lists, debug)

        # 如果没有找到候选类，说明存在继承冲突
        if candidate is None:
            # 抛出异常，无法创建一致的MRO
            raise TypeError("无法创建一致的MRO，存在继承冲突")

        # 将该候选类添加到结果列表
        result.append(candidate)
        # 如果开启调试，打印当前被选中的候选类
        if debug:
            print(f"    选择候选类: {candidate.__name__}")

        # 从所有MRO列表的开头移除候选类
        for mro_list in mro_lists:
            if mro_list and mro_list[0] == candidate:
                mro_list.pop(0)

        # 移除所有已经为空的MRO列表
        mro_lists = [lst for lst in mro_lists if lst]

    # 返回最终合并结果
    return result


# 在MRO列表中查找符合C3算法条件的候选类
def find_candidate(mro_lists, debug=False):
    # 文档字符串，说明查找候选类的规则
    """
    在MRO列表中查找符合条件的候选类

    候选类条件：
    1. 出现在某个列表的头部
    2. 不在任何其他列表的非头部位置出现
    """
    # 遍历每个MRO列表
    for mro_list in mro_lists:
        # 跳过空列表
        if not mro_list:
            continue

        # 获取当前MRO列表的第一个类作为候选
        candidate = mro_list[0]

        # 检查该候选类是否在其它列表的非头部出现
        is_valid = True
        for other_list in mro_lists:
            # 如果候选类出现在任何其他列表的非头部位置
            if candidate in other_list[1:]:
                is_valid = False
                break

        # 如果没有冲突，则返回该候选类
        if is_valid:
            return candidate

    # 若无满足条件的候选类，则返回None
    return None


# 定义测试类A
class A:
    # 空类，测试单继承
    pass


# 定义测试类B，继承自A
class B:
    # 空类，测试单继承
    pass


# 定义测试类C，继承自A和B，测试多重继承
class C(A, B):
    # 空类
    pass


# 测试简单继承情况
# print("=== 简单继承测试 ===")
# print("A 的MRO:", [cls.__name__ for cls in c3_mro_algorithm(A, True)])
# print("B 的MRO:", [cls.__name__ for cls in c3_mro_algorithm(B, True)])

# # 测试多重继承情况
# print("\n=== 多重继承测试 ===")
# print("D 的MRO:", [cls.__name__ for cls in c3_mro_algorithm(C, True)])

# # 比较与Python内置MRO的结果
# print("\n=== 与Python内置MRO比较 ===")
# print("Python的 C.__mro__:", [cls.__name__ for cls in C.__mro__])
# print("我们的算法结果:    ", [cls.__name__ for cls in c3_mro_algorithm(C, True)])
# print("结果一致:", list(C.__mro__) == c3_mro_algorithm(C, True))


# 定义测试类D，继承自B和A
class D(B, A):
    # 空类
    pass


# class E(C, D):
#     pass


# print("A的MRO:    ", [cls.__name__ for cls in c3_mro_algorithm(A, True)])
# print("B的MRO:    ", [cls.__name__ for cls in c3_mro_algorithm(B, True)])
# print("C的MRO:    ", [cls.__name__ for cls in c3_mro_algorithm(C, True)])
print("D的MRO:    ", [cls.__name__ for cls in c3_mro_algorithm(D, True)])
